#pragma once
#include <iostream>

using namespace std;

namespace key
{
	template<class K>
	class BSTreeNode
	{
		template<class K>
		friend class BSTree;

		template<class K>
		friend ostream& operator<<(ostream& cout, BSTreeNode<K>* node);

	public:
		BSTreeNode(const K& val = K(), BSTreeNode* left = nullptr, BSTreeNode* right = nullptr)
			:val(val),
			left(left),
			right(right)
		{}

	private:
		K val = K();
		BSTreeNode<K>* left = nullptr;
		BSTreeNode<K>* right = nullptr;

	};

	template<class K>
	ostream& operator<<(ostream& cout, BSTreeNode<K>* node)
	{
		if (node != nullptr)
			cout << node->key;
		return cout;
	}

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree(Node* root = nullptr)
			:root(root)
		{}

		~BSTree()
		{
			clear();
		}

		BSTree(const BSTree& tree)
		{
			this->root = assign(tree.root);
		}

		BSTree& operator=(BSTree tree)
		{
			//swap(*this, tree); 
			swap(this->root, tree.root);
			return *this;
		}

		Node* assign(Node* n2)
		{
			if (n2 == nullptr)
				return nullptr;
			Node* n = new Node(n2->key);
			n->left = assign(n2->left);
			n->right = assign(n2->right);
			return n;
		}

		void clear()
		{
			_clear(this->root);
		}

		bool insert(const K& x)
		{
			if (root == nullptr)
			{
				root = new Node(x);
				return true;
			}
			Node* ptr = root;
			Node* chi = root;
			while (chi != nullptr)
			{
				if (x > chi->val)
				{
					ptr = chi;
					chi = chi->right;
				}
				else if (x < chi->val)
				{
					ptr = chi;
					chi = chi->left;
				}
				else
					return false;
			}
			if (x < ptr->val)
			{
				ptr->left = new Node(x);
			}
			else
			{
				ptr->right = new Node(x);
			}
			return true;
		}

		void midOrder()
		{
			_midOrder(this->root);
			cout << endl;
		}

		bool isExistence(const K& key)
		{
			Node* cut = this->root;
			while (cut != nullptr)
			{
				if (key > cut->val)
				{
					cut = cut->right;
				}
				else if (key < cut->val)
				{
					cut = cut->left;
				}
				else
					return true;
			}
			return false;
		}

		bool del(const K& key)
		{
			Node* par = nullptr;
			Node* chi = this->root;
			while (chi != nullptr)
			{
				if (key > chi->val)
				{
					par = chi;
					chi = chi->right;
				}
				else if (key < chi->val)
				{
					par = chi;
					chi = chi->left;
				}
				else
				{
					if (chi->left == nullptr)
					{
						if (par == nullptr)
						{
							root = root->right;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->right;
							}
							else {
								par->right = chi->right;
							}
						}
						delete chi;
					}
					else if (chi->right == nullptr)
					{
						if (par == nullptr)
						{
							root = root->left;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->left;
							}
							else {
								par->right = chi->left;
							}
						}
						delete chi;
					}
					else
					{
						Node* ptr = chi;
						Node* cut = chi->right;
						if (cut != nullptr)
						{
							while (cut->left != nullptr)
							{
								ptr = cut;
								cut = cut->left;
							}
							chi->val = cut->val;
							if (ptr->left == cut)
							{
								ptr->left = cut->right;
							}
							else {
								ptr->right = cut->right;
							}
						}
						else
						{
							if (par->left == chi)
							{
								par->left = ptr->left;
							}
							else
							{
								par->right = ptr->left;

							}
						}

						delete cut;
					}
					return true;
				}
			}
			return false;
		}

	private:
		Node* root = nullptr;

		void _midOrder(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			_midOrder(root->left);
			cout << root->val << " ";
			_midOrder(root->right);
		}

		void _clear(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_clear(root->left);
			_clear(root->right);
			delete root;
		}

	};

}

namespace key_val
{
	template<class K, class V>
	class BSTreeNode
	{
		template<class K, class V>
		friend class BSTree;

		template<class K, class V>
		friend ostream& operator<<(ostream& cout, BSTreeNode<K, V>* node);
	public:
		BSTreeNode(const K& key = K(), const V& val = V(), BSTreeNode* left = nullptr, BSTreeNode* right = nullptr)
			:key(key),
			val(val),
			left(left),
			right(right)
		{}

		V getVal()
		{
			return this->val;
		}

	private:
		K key = K();
		V val = V();
		BSTreeNode<K, V>* left = nullptr;
		BSTreeNode<K, V>* right = nullptr;
	};

	template<class K, class V>
	ostream& operator<<(ostream& cout, BSTreeNode<K, V>* node)
	{
		if (node != nullptr)
			cout << node->key << ':' << node->val;
		return cout;
	}


	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree(Node* root = nullptr)
			:root(root)
		{}

		~BSTree()
		{
			clear();
		}

		BSTree(const BSTree& tree)
		{
			this->root =  assign(tree.root);
		}

		BSTree& operator=(BSTree tree)
		{
			//swap(*this, tree); 
			swap(this->root, tree.root);
			return *this;
		}

		Node* assign( Node* n2)
		{
			if (n2 == nullptr)
				return nullptr;
			Node* n = new Node(n2->key,n2->val);
			n->left = assign(n2->left);
			n->right = assign(n2->right);
			return n;
		}

		void clear()
		{
			_clear(this->root);
		}

		bool insert(const K& key, const V& val)
		{
			if (root == nullptr)
			{
				root = new Node(key, val);
				return true;
			}
			Node* ptr = root;
			Node* chi = root;
			while (chi != nullptr)
			{
				if (key > chi->key)
				{
					ptr = chi;
					chi = chi->right;
				}
				else if (key < chi->key)
				{
					ptr = chi;
					chi = chi->left;
				}
				else
				{
					chi->val = val;
					return true;
				}
			}
			if (key < ptr->key)
			{
				ptr->left = new Node(key, val);
			}
			else
			{
				ptr->right = new Node(key, val);
			}
			return true;
		}

		void midOrder()
		{
			_midOrder(this->root);
			cout << endl;
		}

		Node* isExistence(const K& key)
		{
			Node* cut = this->root;
			while (cut != nullptr)
			{
				if (key > cut->key)
				{
					cut = cut->right;
				}
				else if (key < cut->key)
				{
					cut = cut->left;
				}
				else
					return cut;
			}
			return nullptr;
		}

		bool del(const K& key)
		{
			Node* par = nullptr;
			Node* chi = this->root;
			while (chi != nullptr)
			{
				if (key > chi->key)
				{
					par = chi;
					chi = chi->right;
				}
				else if (key < chi->key)
				{
					par = chi;
					chi = chi->left;
				}
				else
				{
					if (chi->left == nullptr)
					{
						if (par == nullptr)
						{
							root = root->right;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->right;
							}
							else {
								par->right = chi->right;
							}
						}
						delete chi;
					}
					else if (chi->right == nullptr)
					{
						if (par == nullptr)
						{
							root = root->left;
						}
						else
						{
							if (par->left == chi)
							{
								par->left = chi->left;
							}
							else {
								par->right = chi->left;
							}
						}
						delete chi;
					}
					else
					{
						Node* ptr = chi;
						Node* cut = chi->right;
						if (cut != nullptr)
						{
							while (cut->left != nullptr)
							{
								ptr = cut;
								cut = cut->left;
							}
							chi->key = cut->key;
							if (ptr->left == cut)
							{
								ptr->left = cut->right;
							}
							else {
								ptr->right = cut->right;
							}
						}
						else
						{
							if (par->left == chi)
							{
								par->left = ptr->left;
							}
							else
							{
								par->right = ptr->left;

							}
						}

						delete cut;
					}
					return true;
				}
			}
			return false;
		}

		

	private:
		Node* root = nullptr;

		void _midOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_midOrder(root->left);
			cout << root << " ";
			_midOrder(root->right);
		}

		void _clear(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_clear(root->left);
			_clear(root->right);
			delete root;
		}

	};

}